The notion of distributed cryptographic protocols has been in cryptography for over fifteen (15) years. Some protocols have been designed to solve communication problems which are impossible from an information-theoretic perspective, like the coin-flipping protocol [B82] and the millionaire-problem protocol [Y82]. Other protocols have been designed to solve generic problems. These protocols (called "general compiler protocols") can securely compute any public function on secure inputs. The first such protocols were developed by Yao [Y86] and Goldreich, Micali and Wigderson [GMW], and various developments were made in subsequent works, e.g., [GHY, K, BGW, CCD].
Recently there has been a thrust to construct more efficient protocols for problems involving the distributed application of cryptographic functions (surveyed in GW97). Function sharing protocols are needed to provide increased memory security, distributed trust, and flexible management (i.e., adding and deleting trustees) of crucial functions like certification authorities and group signatures.
A major efficiency difference between a general compiler protocol (which should be thought of as a plausibility result--see [Gr97]) and a function sharing protocol results from the fact that the communication complexity of the former depends linearly on the actual size of the circuit computing the cryptographic functions, while the communication complexity of the latter is independent of the circuit size (and is typically a polynomial in the input/output size and the number of participants). This difference (pointed out first in FY93, DDFY94) is crucial to practitioners who require efficient protocols. A function sharing protocol involves a protocol for applying the function (based on distributed shares), and sometimes (in what is called a "proactive model") also a protocol for re-randomizing the function shares.
Another important step regarding "distributed cryptographic functions" is the (efficient) distributed generation of the function (the key shares). For cryptographic functions based on modular exponentiation over a field (whose inverse is the discrete logarithm which is assumed to be a one-way function), a protocol for the distributed generation of keys was known [P2]. However, for the RSA function and related cryptographic functions to be described below, which requires the generation of a product of two primes and an inverse of a public exponent, this step was an open problem for many years. Note that Yao's central motivation [Y86] is introducing general compiler protocols that "computer circuits securely in communication" was the issue of distributed generation of RSA keys. Indeed the results of [Y86, GMW] show the plausibility of this task.
Another step forward was achieved by Boneh and Franklin [BF97] who showed how a set of participants can generate an RSA function efficiently, thus detouring the inefficient compiler. They showed that their protocol was secure in the limited model of "trusted but curious" parties. They left open the issue of robustness, i.e., generation in the presence of misbehaving (malicious) parties. If adversaries misbehave arbitrarily, the Boneh-Franklin protocol may be prevented from ever generating a shared RSA key (due to lack of robustness).
The following references provide additional background for the invention.
[ACGS] W. Alexi, B. Chor, O. Goldreich and C. Schnorr. RSA and Rabin Functions: Certain Parts are as Hard as the Whole. In SIAM Journal of Computing, volume 17, n. 2, pages 194-209, April 1988. PA0 [B84] E. Bach, "Discrete Logarithms and Factoring", Tech. Report No. UCB/CSD 84/186. Computer Science Division (EECS), University of California, Berkeley, Calif., June 1984. PA0 [BGW] Ben-Or M., S. Goldwasser and A. Wigderson, Completeness Theorem for Non cryptographic Fault-tolerant Distributed Computing, STOC 1988, ACM, pp. 1-10. PA0 [B82] M. Blum, "Coin flipping by telephone: a protocol for solving impossible problems," IEEE Computer Conference 1982, 133-137. PA0 [BF97] D. Boneh and M. Franklin, Efficient Generation of Shared RSA Keys, Crypto 97, pp. 425-439. PA0 [B88] C. Boyd, Digital Multisignatures, IMA Conference on Cryptography and Coding, Claredon Press, 241-246 (eds. H. Baker and F. Piper), 1986. PA0 [BCLL] G. Brassard, C. Crepeau, S. Laplante, C. Leger. Computationally Convincing proofs of knowledge, In Proceedings of the 8.sup.th Symp. On Theoretical Aspects of Computer Science (Springer, Berlin, 1991), pp. 251-262. PA0 [BGM] E. Brickell, D. Gordon and K. McCurley. Fast Exponentiation with Precomputation Advances in Cryptology--Eurocrypt 92 Proceedings, Lecture Notes in Computer Science, Vol. 658, R. Rueppel ed., Springer-Verlag, 1992. PA0 [CCD] D. Chaum, C. Crepeau and I. Damgard, Multiparty Unconditionally Secure Protocols, STOC 1988, ACM, pp. 11-19. PA0 [CEG] D. Chau, M.-H. Evertse and J. van de Graff, Multiparty computations ensuring privacy of each party's input and correctness of the result, Advances in Cryptology--Europcrypt 88 Proceedings, Lecture Notes in Computer Science, Vol. 330, C. Gunther ed., Springer-Verlag, 1988 pp. 87-119. PA0 [CEGP] D. Chaum, J.-H. Evertse, J van de Graaf and R. Peralta, An improved protocol for demonstrating possession of discrete logarithms and some generalizations, Advances in Cryptology--Crypto 86 Proceedings, Lecture Notes in Computer Science, Vol. 263, A. Odlyzko ed., Springer-Verlag, 1986, pp. 200-212. PA0 [CGMA] B. Chor, S. Goldwasser, S. Micali and B. Awerbuch, Verifiable Secret Sharing and Achieving Simultaneous Broadcast, Proceedings of the 26.sup.th Symposium on Foundations of Computer Science, IEEE, 1985, pp. 335-344. PA0 [DDFY94] A. DeSantis, Y. Desmedt, Y. Frankel and M. Yung, How to Share a Function Securely, ACM Proceedings of the 26.sup.th Annual Symposium on Theory of Computing, ACM, 1994, pp. 522-533. PA0 [DF89] Y. Desmedt and Y. Frankel, Threshold cryptosystems, Advances in Cryptology--Crypto 89 Proceedings, Lecture Notes in Computer Science, Vol. 435, G. Brassard ed., Springer-Verlag, 1989, pp. 307-315. PA0 [DH] W. Diffle and M. Hellman, New Directions in Cryptography, IEEE Trans. On Information Theory 22(6), 1976, pp. 644-654. PA0 [FFS] U. Feige, A. Fiat and A. Shamir, Zero-Knowledge Proof of Identity,. Proceedings of the Nineteenth annual ACM symp. Theory of Computing, 1987, pp. 210-217. PA0 [F] P. Feldman, A Practical Scheme for Non-Interactive Certifiable Secret Sharing, Proceedings of the 28.sup.th Symposium on Foundations of Computer Science, IEEE, 1987, pp. 427-437. PA0 [FS86] A. Fiat and A. Shamir, "How to prove yourself: Practical solutions to identification and signature problems," in Advances in Cryptology--CRYPTO '86 Proceedings (Lecture Notes in Computer Science, Vol. 263), ed. A. Odlyzko 186-194, Springer-Verlag, New York, 1987. PA0 [FGY] Y. Frankel, P. Gemmell and M. Yung, Witness Based Cryptographic Program Checking and Robust Function Sharing, Proceedings of the 28.sup.th Annual Symposium on Theory of Computing, ACM 1996, pp. 499-508. PA0 [FGMY] Y. Frankel, P. Gemmel, P. MacKenzie and M. Yung, Proactive RSA, Crpto 97. PA0 [FGMYa] Y. Frankel, P. Gemmel, P. MacKenzie and M. Yung, Optimal Resilience Proactive Public-Key Cryptosystems, FOCS 97. PA0 [FS89] U. Feige and A. Shamir, Zero knowledge proofs of knowledge in two rounds, CRYPTO 1989, 20-24. PA0 [FY93] M. Franklin and M. Yung, Secure and Efficient Off-line Digital Money, Porch. Of the 20.sup.th Int. Col. On Automata, Languages and Programming (ICALP), 1993, LNCS 700, Springer-Verlag, pp. 265-276. PA0 [GHY] Z. Galil, S. Haber, and M. Yung, Minimum-Knowledge Interactive Proof for Decision Problems, SIAM j. Comp., 18, 9189, pp. 711-739. PA0 [GHY85] Z. Galil, S. Haber and M. Yung, Symmetric Public-Key Cryptography, Crypto 85. PA0 [GHY87] Z. Galil, S. Haber and M. Yung, Cryptographic Computations: Secure Fault Tolerant Protocols in the Public Key Model, Crypto 87, pp. 135-155. PA0 [GJKR] R. Gennaro, S. Jarecki, H. Krawczyk, T. Rabin, Robust Threshold DSS Signatures, Advances in Cryptology--Eurocrypt 96 Proceedings, Lecture Notes in Computer Science, Vol. 1070, U. Maurer ed., Springer-Verlag, 1996, pp. 354-371. PA0 [Gr97] O. Goldreich, On Foundations of Modern Cryptography, an invited paper, Crypto 97. PA0 [GMW86] O. Goldreich, S. Micali and A. Wigderson, "Proofs that yield nothing but their validity and a methodology of cryptographic protocol design," IEEE FOCS 1986, pp. 174-187. PA0 [GMW] O. Goldreich, S. Micali, and A. Wigderson, How to play any mental game, Proceedings of the Nineteenth annual ACM Symp. Theory of Computing, 1987, pp. 218-229. PA0 [Gw97] S. Goldwasser, A New Direction in Cryptography: Twenty something years after, an invited paper, FOCS 97. PA0 [GMR] A. Goldwasser, S. Micali and C. Rackoff, The Knowledge Complexity of Interactive Proof-Systems, Siam J. on Computing, 18(1) (1989), pp. 186-208. PA0 [HW] G. Hardy and E. Wright, An introduction to the theory of numbers, Oxford Science Publications, London, Great Britain, fifth ed., 1985. PA0 [HJJKY] A. Herzberg, M. Jakobsson, S. Jarecki, H. Krawczyk, M. Yung, Proactive Public-Key and Signature Schemes, Proceedings of the Fourth Annual Conference on Computer and Communications Security, ACM, 1996. PA0 [IY87] R. Impagliazzo, and M. Yung, "Direct minimum-knowledge computation," in Advances in Cryptology--CRYPTO '87 Proceedings (Lecture Notes in Computer Science, Vol. 293), ed. C. Pomerance, 40-51, Springer-Verlag, New York, 1988. PA0 [K] J. Kilian, "Founding cryptography on oblivious transfer," ACM STOC 1988, 20-31. PA0 [M76] G. Miller, Riemann's Hypothesis and Test of Primality, J. of Comp. And Syst. Sciences, 13, 300-317, 1976. PA0 [OK92] T. Okamoto, Provably Secure and Practical Identification and Corresponding Signature Scheme, Advances in Cryptology--Crypto 92 Proceedings, Lecture Notes in Computer Science Vol. 740, E. Brickell ed., Springer-Verlag, 1992, pp. 31-53. PA0 [OY91] R. Ostrovsky and M. Yung, How to withstand mobile virus attacks, Proc. of the 10.sup.th ACM Symposium on the Principles of Distributed Computing, 1991, pp. 51-61. PA0 [P] T. P. Pedersen, Distributed Provers with Applications to Undeniable Signatures, Advances in Cryptology--Eurocrypt 91 Proceedings, Lecture Notes in Computer Science Vol. 547, D. Davies ed., Springer-Verglag, 1991, pp. 221-242. PA0 [P2] T. P. Pedersen, A threshold cryptosystem without a trusted party, Advances in Cryptology--Eurocrypt 91 Proceedings, Lecture Notes in Computer Science Vol. 547, D. Davies ed., Springer-Verlag, 1991, pp. 129-140. PA0 [P91] T. P. Pedersen, Non-interactive and information theoretic secure verifiable secret sharing, Advances in Cryptology--Crypto 91 Proceedings, Lecture Notes in Computer Science Vol. 576, J. Feigenbaum ed., Springer-Verlag, 1991, pp. 129-140. PA0 [RSA] R. Rivest, A. Shamir and L. Adleman, A Method for Obtaining Digital Signature and Public Key Cryptosystems, Comm. of ACM, 21 (1978), pp. 120-126. PA0 [Sh] A Shamir, How to share a secret, Comm. of ACM, 22 (1979), pp. 612-613. PA0 [Y82a] A. C. Yao, Theory and Applications of Trapdoor functions, Proceedings of the 23rd Symposium on the Foundation of Computer Science, 1982, pp. 80-91. PA0 [Y82] A. C. Yao, "Protocols for secure computations", IEEE FOCS 1982, 160-164. PA0 [Y86] A. C. Yao, "How to generate and exchange secrets", IEEE FOCS 1986, 162-167.